import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * Date: 2024-02-02
 * Time:14:59
 */
public class BinaryTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public int nodesize;

    public int leafsize;

    int getLeafNodeCount1(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right);
    }

    int getLeafNodeCount2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            ++leafsize;
        }
        getLeafNodeCount2(root.right);
        getLeafNodeCount2(root.left);
        return this.leafsize;
    }

    int getHeight(TreeNode root) {
        if(root == null)
            return 0;
        int max1 = getHeight(root.left);
        int max2 = getHeight(root.right);
        return max1 > max2? max1+1 : max2+1;
    }

    TreeNode find(TreeNode root,char val) {
        if(root == null)
            return null;
        if(root.val == val)
            return root;
        TreeNode ret = find(root.left,val);
        if(ret != null) {
            return ret;
        }
        ret = find(root.right,val);
        return ret;
    }

    Queue<TreeNode> queue = new LinkedList<>();

    void LevelOrder(TreeNode root) {
        if(root == null)
            return;
        System.out.println(root.val);
        queue.offer(root.left);
        queue.offer(root.right);
        LevelOrder(queue.poll());
        LevelOrder(queue.poll());
    }

    void PreOrderNorR(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }

    }

    void InOrderNorR(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }
}
